//
// Created by Tan Ke on 2024/1/15.
//

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

int calcPaths(int** recordMap, int i, int j, int m, int n)
{
    if (recordMap[i][j] != 0) {
        return recordMap[i][j];
    }

    if (i == 0) {
        recordMap[0][j] = calcPaths(recordMap, 0, j - 1, m, n);
        return recordMap[0][j];
    }
    if (j == 0) {
        recordMap[i][0] = calcPaths(recordMap, i - 1, j, m, n);
        return recordMap[i][0];
    }
    recordMap[i][j] = calcPaths(recordMap, i - 1, j, m, n) + calcPaths(recordMap, i, j - 1, m, n);
    return recordMap[i][j];
}

int uniquePaths(int m, int n)
{
    int** recordMap = (int**)malloc(sizeof(int*) * m);
    for (int i = 0; i < m; i ++) {
        int *row = (int*)malloc(sizeof(int) * n);
        for (int j = 0; j < n; j ++) {
            row[j] = 0;
        }
        recordMap[i] = row;
    }

    // 初始化
    for (int i = 0; i < m; i ++) {
        recordMap[i][0] = 1;
    }
    for (int j = 0; j < n; j ++) {
        recordMap[0][j] = 1;
    }

    return calcPaths(recordMap, m - 1, n - 1, m, n);
}


int main(void)
{
    return 0;
}